0367. 有效的完全平方数【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 二分查找

1. 📝 题目描述

• leetcode

给你一个正整数 num。如果 num 是一个完全平方数，则返回 true，否则返回 false。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt。

---

示例 1：

输入：num = 16
输出：true
解释：返回 true，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

---

提示：

• 1 <= num <= 2^31 - 1

2. 🎯 s.1 - 二分查找

js

/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function (num) {
  if (num === 1) return true

  let left = 1

  // 二分查找 - 边界优化 - 缩小搜索空间
  let right = Math.floor(num / 2)
  // 对于 num > 1，完全平方数的平方根不会超过 num/2（当 num >= 4 时严格成立）

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    let square = mid * mid

    if (square === num) {
      return true
    } else if (square < num) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return false
}

• 时间复杂度：$O(\log n)$，二分查找的时间复杂度
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间
• 算法思路：
  • 特殊情况处理：当 num 为 1 时，直接返回 true
  • 搜索范围优化：对于大于 1 的数，其平方根不会超过 num/2，所以右边界设为 Math.floor(num / 2)
    • 🤔 为什么 Math.floor(num / 2) 是安全的？
    • 对于 num = 1 → 特殊情况已经判定了，不会进入后续的二分查找循环中
    • 对于 num = 2, 3 → 虽然 sqrt(num) > num/2，但它们不是完全平方数 → 二分查找找不到，返回 false，结果正确
    • 对于 num ≥ 4 → sqrt(num) ≤ num/2，搜索区间 [1, num/2] 包含真实解
    • 其实这个搜索区间还是太大了，还可以进一步优化，比如写成：let right = Math.floor(Math.sqrt(num)) + 1，但是这么写不符合题目的要求 —— 不要使用内置的 sqrt。
  • 二分查找：
    • 计算中间值 mid 的平方
    • 如果平方等于 num，则找到了完全平方根，返回 true
    • 如果平方小于 num，说明平方根在右半部分，调整左边界
    • 如果平方大于 num，说明平方根在左半部分，调整右边界
  • 结束条件：当 left > right 时，搜索结束，返回 false